#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int knightDialer(int n) {
        if (n == 1) return 10;
        int mod = 1e9 + 7;
        vector<vector<int>> dp(n, vector<int>(10));
        for (int i = 0; i < 10; i++) dp[0][i] = 1;
        dp[0][5] = 0;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                if (j == 0)
                {
                    dp[i + 1][4] = (dp[i + 1][4] + dp[i][j]) % mod;
                    dp[i + 1][6] = (dp[i + 1][6] + dp[i][j]) % mod;
                }
                else if (j == 1)
                {
                    dp[i + 1][6] = (dp[i + 1][6] + dp[i][j]) % mod;
                    dp[i + 1][8] = (dp[i + 1][8] + dp[i][j]) % mod;
                }
                else if (j == 2)
                {
                    dp[i + 1][7] = (dp[i + 1][7] + dp[i][j]) % mod;
                    dp[i + 1][9] = (dp[i + 1][9] + dp[i][j]) % mod;
                }
                else if (j == 3)
                {
                    dp[i + 1][4] = (dp[i + 1][4] + dp[i][j]) % mod;
                    dp[i + 1][8] = (dp[i + 1][8] + dp[i][j]) % mod;
                }
                else if (j == 4)
                {
                    dp[i + 1][0] = (dp[i + 1][0] + dp[i][j]) % mod;
                    dp[i + 1][3] = (dp[i + 1][3] + dp[i][j]) % mod;
                    dp[i + 1][9] = (dp[i + 1][9] + dp[i][j]) % mod;
                }
                else if (j == 5) continue;
                else if (j == 6)
                {
                    dp[i + 1][0] = (dp[i + 1][0] + dp[i][j]) % mod;
                    dp[i + 1][1] = (dp[i + 1][1] + dp[i][j]) % mod;
                    dp[i + 1][7] = (dp[i + 1][7] + dp[i][j]) % mod;
                }
                else if (j == 7)
                {
                    dp[i + 1][2] = (dp[i + 1][2] + dp[i][j]) % mod;
                    dp[i + 1][6] = (dp[i + 1][6] + dp[i][j]) % mod;
                }
                else if (j == 8)
                {
                    dp[i + 1][1] = (dp[i + 1][1] + dp[i][j]) % mod;
                    dp[i + 1][3] = (dp[i + 1][3] + dp[i][j]) % mod;
                }
                else if (j == 9)
                {
                    dp[i + 1][2] = (dp[i + 1][2] + dp[i][j]) % mod;
                    dp[i + 1][4] = (dp[i + 1][4] + dp[i][j]) % mod;
                }
            }
        }
        int ret = 0;
        for (int j = 0; j < 10; j++) ret = (ret + dp[n - 1][j]) % mod;
        return ret;
    }
};